package com.test;

import java.io.BufferedReader;

import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;
import java.util.NavigableMap;
import java.util.TreeMap;

public class LangTrans {

	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception{
		new LangTrans().run();

	}
	
	TreeMap<String,String> inputMap = new TreeMap<String,String>();
  List<Rule> rules = new ArrayList<>();

	void run() throws Exception{
		InputStream in = this.getClass().getClassLoader().getResourceAsStream("lang-trans.txt");
	  BufferedReader br = new BufferedReader(new InputStreamReader(in));
	  String line="";
	  while((line=br.readLine())!=null){
	      System.out.println(line);
	      line = line.trim();
	      if( line.isEmpty() || line.startsWith("#") ){
	      }else if( line.startsWith("==========") ){
          line = line.substring("==========".length());
          String from = line.substring(0,line.indexOf('='));
          String toAnswer = line.substring(line.indexOf('=')+1);
          boolean ok=false;
          for( Rule r : rules ){
            String tr = r.translate(from);
            if( tr!=null ){
              System.out.println("by Rule "+r);
              System.out.println(from + " ===> "+tr);
              if( !tr.equals(toAnswer) ){
                throw new IllegalStateException();
              }
              ok=true;
            }
          }
          if( !ok ){
            System.out.println("failed to translate: "+from);
            throw new IllegalStateException();
          }
	    	  //System.out.println("QUEST - not yet implemented");
	      }else{
	    	  //System.out.println("trying "+line);
	    	  String from = line.substring(0,line.indexOf('='));
	    	  String to = line.substring(line.indexOf('=')+1);

          scanSimilarHead(from, to);
          scanSimilarTailMap(from, to);
          scanSimilarHeadMap(from, to);

	    	  inputMap.put(from, to);
	      }
	  }
    System.currentTimeMillis();
	}

  private void scanSimilarHead(String from, String to) {
    List<String> prevKeys = Collections.emptyList();
    for( int i=from.length()-1; i>=1; i-- ){
      String head = from.substring(0,i);
      List<String> startKeys = startingKeys(head);
      if( startKeys.size()>prevKeys.size() ){
        deriveHeadRule(from, to, head, startKeys);
        prevKeys = startKeys;
      }else{
        //System.out.println(from + " ("+head+")" + " has no new similar "+startKeys);
      }
    }
  }

  void scanSimilarTailMap(String from, String to) {
    List<String> prevKeys = Collections.emptyList();
    for( int i=1; i<from.length(); i++ ){
      String tail = from.substring(i);
      List<String> endKeys = endingKeys(tail);
      if( endKeys.size()>prevKeys.size() ){
        //deriveHeadRule(from, to, head, startKeys);
        //System.out.println("**** " + from + " ("+tail+")" + " has similar "+endKeys);
        for( String endK : endKeys ){
          String commonEnd = commonEnding(to, inputMap.get(endK));
          if( commonEnd.length()>0 ){
            HeadsMapRule r = new HeadsMapRule();
            r.tailFrom = tail;
            r.tailTo = commonEnd;
            r.put(from, to);
            r.put(endK, inputMap.get(endK));
            r = r.add(rules);
            System.out.println(r);

//            System.out.println("**** " + from + " ("+tail+")" + " has similar '"+endK
//                + "' tail '"+commonEnd+"'");
          }
        }
        prevKeys = endKeys;
      }else{
        //System.out.println(from + " ("+head+")" + " has no new similar "+startKeys);
      }
    }
  }

  void scanSimilarHeadMap(String from, String to) {
    List<String> prevKeys = Collections.emptyList();
    for( int i=from.length()-1; i>=0; i-- ){
      String head = from.substring(0,i);
      List<String> startKeys = startingKeys(head);
      if( startKeys.size()>prevKeys.size() ){
        for( String endK : startKeys ){
          String commonStart = commonStart(to, inputMap.get(endK));
          if( commonStart.length()>0 ){
            TailsMapRule r = new TailsMapRule();
            r.headFrom = head;
            r.headTo = commonStart;
            r.put(from, to);
            r.put(endK, inputMap.get(endK));
            r = r.add(rules);
            System.out.println(r);
          }
        }
        prevKeys = startKeys;
      }else{
        //System.out.println(from + " ("+head+")" + " has no new similar "+startKeys);
      }
    }
  }

  String commonStart(String a, String b){
    for( int i = Math.min(a.length(), b.length()); i>=0; i-- ){
      String ai = a.substring(0,i);
      String bi = b.substring(0,i);
      if( ai.equals(bi) ){
        return ai;
      }
    }
    return "";
  }

  String commonEnding(String a, String b){
    for( int i = Math.min(a.length(), b.length()); i>=0; i-- ){
      String ai = a.substring(a.length()-i);
      String bi = b.substring(b.length()-i);
      if( ai.equals(bi) ){
        return ai;
      }
    }
    return "";
  }

  abstract class Rule{
    abstract String translate(String orig);
  }
  class HeadRule extends Rule{
    String tailFrom;
    String tailTo;

    @Override
    public String toString() {
      return "HeadRule{" +
          "tailFrom='" + tailFrom + '\'' +
          ", tailTo='" + tailTo + '\'' +
          '}';
    }

    @Override
    String translate(String orig) {
      if( orig.endsWith(tailFrom) ){
        String v = inputMap.get(orig.substring(0, orig.length()-tailFrom.length()));
        if( v!=null ){
          return v + tailTo;
        }
      }
      return null;
    }
  }
  
  class HeadsMapRule extends Rule{
    String tailFrom;
    String tailTo;
    Map<String,String> headsMap = new HashMap<>();
    HeadsMapRule mapBaseRule;

    @Override
    String translate(String orig) {
      if( orig.endsWith(tailFrom) ){
        String key = orig.substring(0, orig.length()-tailFrom.length());
        if( headsMap.containsKey(key) ){
          return headsMap.get(key) + tailTo;
        }
        if( mapBaseRule!=null && mapBaseRule.headsMap.containsKey(key) ){
          return mapBaseRule.headsMap.get(key) + tailTo;
        }
      }
      return null;
    }

    void put(String from, String to){
      if( ! from.endsWith(tailFrom) ){
        throw new IllegalArgumentException();
      }
      if( ! to.endsWith(tailTo) ){
        throw new IllegalArgumentException();
      }
      headsMap.put(from.substring(0, from.length()-tailFrom.length()),
          to.substring(0, to.length()-tailTo.length()));

    }

    HeadsMapRule add(List<Rule> rules){
      for( Object o : rules ){
        if( o instanceof HeadsMapRule ){
          HeadsMapRule r = (HeadsMapRule)o;
          if( r.tailFrom.equals(tailFrom) && r.tailTo.equals(tailTo) ){
            r.headsMap.putAll(headsMap);
            return r;
          }
        }
      }
      for( Object o : rules ){
        if( o instanceof HeadsMapRule ){
          HeadsMapRule r = (HeadsMapRule)o;
          if( r.headsMap.entrySet().containsAll(headsMap.entrySet()) ){
            mapBaseRule = r;
            break;
          }
        }
      }
      rules.add(this);
      return this;
    }

    @Override
    public String toString() {
      return "HeadsMapRule{" +
          "'{a}" + tailFrom + "\'->" +
          "'{m(a)}" + tailTo + '\'' +
          ", headsMap=" + headsMap +
          '}';
    }
  }

  class TailsMapRule extends Rule{
    String headFrom;
    String headTo;
    Map<String,String> tailsMap = new HashMap<>();
    TailsMapRule mapBaseRule;

    @Override
    String translate(String orig) {
      if( orig.startsWith(headFrom) ){
        String key = orig.substring(headFrom.length());
        if( tailsMap.containsKey(key) ){
          return headTo + tailsMap.get(key);
        }
        if( mapBaseRule!=null && mapBaseRule.tailsMap.containsKey(key) ){
          return headTo + mapBaseRule.tailsMap.get(key);
        }
      }
      return null;
    }

    void put(String from, String to) {
      if( ! from.startsWith(headFrom) ){
        throw new IllegalArgumentException();
      }
      if( ! to.startsWith(headTo) ){
        throw new IllegalArgumentException();
      }
      tailsMap.put(from.substring(headFrom.length()),
          to.substring(headTo.length()));

    }

    TailsMapRule add(List<Rule> rules){
      for( Object o : rules ){
        if( o instanceof TailsMapRule ){
          TailsMapRule r = (TailsMapRule)o;
          if( r.headFrom.equals(headFrom) && r.headTo.equals(headTo) ){
            r.tailsMap.putAll(tailsMap);
            return r;
          }
        }
      }
      for( Object o : rules ){
        if( o instanceof TailsMapRule ){
          TailsMapRule r = (TailsMapRule)o;
          if( r.tailsMap.entrySet().containsAll(tailsMap.entrySet()) ){
            mapBaseRule = r;
            break;
          }
        }
      }
      rules.add(this);
      return this;
    }

    @Override
    public String toString() {
      return "TailsMapRule{" +
          "'" + headFrom + "{a}'->" +
          "'" + headTo +"{m(a)}'" +
          ", tailsMap=" + tailsMap +
          ", base=" + mapBaseRule +
          '}';
    }
  }

  void deriveHeadRule(String from, String to, String head, List<String> startKeys){
    //System.out.println(from + " ("+head+")" + " has similar "+startKeys);
    for( String startK : startKeys ){
      String startKMapping = inputMap.get(startK);
      if( to.startsWith(startKMapping) ){
        HeadRule hr = new HeadRule();
        hr.tailFrom = from.substring(head.length());
        hr.tailTo = to.substring(startKMapping.length());
        System.out.println(hr.toString());
        rules.add(hr);
      }
    }
  }

  List<String> endingKeys(String ending){
    List<String> ret = new ArrayList<String>();
    for( String s : inputMap.keySet() ){
      if( s.endsWith(ending) ){
        ret.add(s);
      }
    }
    return ret;
  }

	List<String> startingKeys(String starting){
	  List<String> ret = new ArrayList<String>(); 
	  NavigableMap<String,String> tailMap = inputMap.tailMap(starting,true);
	  if( !tailMap.isEmpty() ){
		  for( Map.Entry<String, String> me : tailMap.entrySet() ){
			if( !me.getKey().startsWith(starting) ){
				break;
			}
			ret.add(me.getKey());
			//System.out.println(from + " ("+head+")" + " has similar "+me.getKey());
		  }
		  
	  }
	  return ret;
	}
}
